#include <stdio.h>
#include <cstring>

void getK(const char* ptn,int K[])
{
	K[0]=-1;
	int i=0,j=-1;
	int len=strlen(ptn);
	
	while(i<len)
	{
		if(j==-1 || ptn[i]==ptn[j])
		{
			i++;j++;
			K[i]=j;
		}
		else
		{
			j=K[j];
		}
	}
}
void printK(int K[],int n)
{
	for(int i=0;i<n;i++)
	{
		printf("%d ",K[i]);
	}
	printf("\n");
}
int strKMP(const char* src,const char* ptn)
{
	if(src==0 || ptn==0)
		return 0;
	int len_src=strlen(src);
	int len_ptn=strlen(ptn);
	const int maxsize=10;
	int k[maxsize];
	getK(ptn,k);
	
	int i=-1,j=-1;
	while(i<len_src)
	{
		if(j==-1 || src[i]==ptn[j])
		{
			i++;j++;
			if(j==len_ptn)
			{
				return i-len_ptn;
			}
		}
		else
		{
			j=k[j];
		}
	}
	return -1;
}
int main()
{
	int K[7];
	getK("abcabcd",K);
	printK(K,7);
	
	printf("%d\n",strKMP("hello","el"));
	
	return 0;
}
